#pragma once
#include<vector>
#include<list>
#include<set>
#include<iostream>

using namespace std;
namespace close_address
{
//这三个状态缺一不可，特别我们会容易忽略DELETE，感觉它可有可无，其实不然，因为在查找的时候，是通过对找的值进行取模，然后确定取模后值的位置，然后依次找，直到遇见空结束，如果没有DELETE状态，我们可能永远找不到有些值（如果我们没有设置DELETE状态，肯定会把删除的值的位置状态设置为空）
enum Status
{
    EMPTY,
    EXIST,
    DELETE
};

//哈希表里存储的数据类型
template<class K,class V>
struct HashData
{
    pair<K,V> _kv;
    Status _s=EMPTY;//初始时状态都是EMPTY
};

//仿函数，主要是将关键字不是整数转为整数
template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
    {
      return (size_t)key;
  }
};
//仿函数string版本2
//为了实现，在插入string类型时，不需要手动的传入仿函数，我们可以对仿函数进行特化
template<>
struct HashFunc<string>
{
  size_t operator()(const string& key)
    {
      size_t hash=0;
      for(auto e:key)
      {
          hash+=e;//这里还是有缺陷，如果插入的字符串“abc”和“acb”，他们转出的整形值都是一样的
          hash*=31;//这里就是为了解决这种冲突，但只是减少冲突，冲突永远存在，因为整形的值是有限的，但是字符串的可能性无穷多
      }
      return hash;
  }
};

//仿函数string版本1
//struct HashFuncString
//{
//  size_t operator()(const string& key)
//    {
//      size_t hash=0;
//      for(auto e:key)
//      {
//          hash+=e;//这里还是有缺陷，如果插入的字符串“abc”和“acb”，他们转出的整形值都是一样的
//          hash*=31;//这里就是为了解决这种冲突，但只是减少冲突，冲突永远存在，因为整形的值是有限的，但是字符串的可能性无穷多
//      }
//      return hash;
//  }
//};

//哈希表——闭散列
template<class K,class V,class Hash=HashFunc<K>>//Hash仿函数用于关键字为非整形时，转为整形
class HashTable
{
public:
    HashTable()
    {
        _tables.resize(10);//将vector有效数据个数扩展10都以0初始化
    }
    bool Insert(const pair<K,V>& kv)
    {
        
        if(Find(kv.first))
            return false;
        //负载因子
        //负载因子太大，冲突会剧增，冲突增加，效率降低（例如90%）
        //负载因子太大，冲突会降低，空间利用率低（例如30%）
        if(_n*10/_tables.size()==7)//因为_n和size都是整形，是不可能结果是小数，
        {
            //不能直接扩容，因为值的映射关系已经发生变化了，_tables.size()变了
            //只能开新空间，重新映射，再释放旧空间
            size_t newSize=_tables.size()*2;//新开辟一段空间原来的2倍
            HashTable<K,V,Hash> newHT;//创建一个新的哈希表????
            newHT._tables.resize(newSize);//给新的哈希表开辟新的空间
            //遍历久表
            for(size_t i=0;i<_tables.size();i++)//将原来的哈希表中数据一一映射到新的哈希表
            {
                if(_tables[i]._s==EXIST)//如果下标为i位置的数据的状态存在
                {
                    newHT.Insert(_tables[i]._kv);//将数据插入到新表中，按照新的映射关系插入
                }
            }
            _tables.swap(newHT._tables);//将两个顺序表进行交换
        }
        
        Hash hf;//仿函数对象
        
        //线性探测
        size_t hashi=hf(kv.first)%_tables.size();//对插入的关键字进行映射，采用的是初留余数法
        while(_tables[hashi]._s==EXIST)//判断该位置是否被占用
        {
            hashi++;//如果该位置被占用，就线性探测，向前走一步
            hashi%=_tables.size();//防止越界了
        }
        
        _tables[hashi]._kv=kv;//线性探测，找到空位置，就插入值
        _tables[hashi]._s=EXIST;//然后改变此位置的状态为EXIST
        _n++;//关键字个数+1
        return true;
    }
    
    HashData<K, V>* Find(const K&key)
    {
        Hash hf;//仿函数对象
        size_t hashi=hf(key)%_tables.size();//查找的关键字进初留余数法
        while(_tables[hashi]._s!=EMPTY)//如果该位置为空，表示没有改关键字的数据
        {
            
            if(_tables[hashi]._s!=DELETE&&_tables[hashi]._kv.first==key)//这种写法严谨
            //if(_tables[hashi]._kv.first==key)//这种写法是不严谨的，因为如果一个值被删除后，我们采用删除并不真正的删除，而是修改删除位置的状态，所以我们只判断该位置的关键字和我们查找的关键字是否相同是不严谨的，还需要判断该位置是否已经为删除状态
            {
                return &_tables[hashi];//找到后返回改数据的地址
            }
            
            hashi++;//如果没有找到，线性探测，直到遇见位置的状态为EMPTY停止
            hashi%=_tables.size();//防止越界
        }
    
        return nullptr;
    }
    
    bool Erase(const K& key)
    {
        HashData<K, V>* ret=Find(key);//删除之前找到改关键字的位置
        if(ret)
        {
            ret->_s=DELETE;//找到该关键字数据位置后，将状态设置为DELETE
            _n--;//关键字个数-1
            return true;
        }
        return false;
    }
    
    void Print()
    {
        for(size_t i=0;i<_tables.size();i++)
        {
            if(_tables[i]._s==EXIST)
            {
                cout<<"["<<i<<"]->"<<_tables[i]._kv.first<<":"<<_tables[i]._kv.second<<endl;
            }
            else if(_tables[i]._s==EMPTY)
            {
                printf("[%zu]->E\n",i);
            }
            else
            {
                printf("[%zu]->D\n",i);
            }
        }
    }
    size_t size()//返回关键字个数
    {
        return _n;
    }
private:
    vector<HashData<K,V>> _tables;
    size_t _n=0;//存储关键字的个数
};

void TestHT1()//测试闭散列的哈希表
{
    HashTable<int,int> ht;
    int a[]={4,14,1};
    for(auto e: a)
    {
        ht.Insert(make_pair(e,e));
    }
    
    ht.Insert(make_pair(3,3));
    ht.Insert(make_pair(-3,-3));
    ht.Insert(make_pair(78,78));
    ht.Print();

    ht.Erase(3);
    ht.Print();
    ht.Insert(make_pair(3,3));
    ht.Print();
}
void TestHT2()//测试闭散列的哈希表
{
    string arr[]={"苹果","香蕉","葡萄","芒果","水蜜桃","猕猴桃","胡桃","香蕉","葡萄","芒果","芒果","水蜜桃","猕猴桃","胡桃","香蕉","葡萄","芒果"};

    HashTable<string,int> ht;

    for(auto& ch:arr)
    {
        auto ret=ht.Find(ch);
        if(ret)
        {
            ret->_kv.second++;
        }
        else
        {
            ht.Insert(make_pair(ch, 1));
        }
    }

    ht.Print();
}
}

//这是设计开散列——哈希桶的哈希表的一种方案，采用的stl中的list结构方案，但是这种方案有点空间浪费，因为这里面的链表是双向链表，但实现哈希表只需要单链表
//namespace hash_bucket
//{
//    template<class K,class V>
//struct HashNode
//{
//
//};
//
//template<class K,class V>
//class HashTable
//{
//    typedef HashNode<K, V> Node;
//private:
//    struct bucket
//    {
//        list<pair<K, V>> _lt;
//        set<pair<K, V>> _rbtree;
//        size_t len=0;//桶中的数据，如果数据个数小于8，用链表存储，如果大于8用set存储
//    };
//    vector<bucket> _tables;
//    size_t _n;
//};
//}


//开散列——哈希桶的哈希表
namespace hash_bucket
{
//哈希表存储的数据类型
template<class K,class V>
struct HashNode
{
    HashNode<K,V>* next;//节点指针
    pair<K, V> _kv;
    
    HashNode(const pair<K, V>& kv):_kv(kv)
    ,next(nullptr)
    {}
};

//仿函数
template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
    {
      return (size_t)key;
  }
};

//为了实现，在插入string类型时，不需要手动的传入仿函数，我们可以对仿函数进行特化
template<>
struct HashFunc<string>
{
  size_t operator()(const string& key)
    {
      size_t hash=0;
      for(auto e:key)
      {
          hash+=e;//这里还是有缺陷，如果插入的字符串“abc”和“acb”，他们转出的整形值都是一样的
          hash*=31;//这里就是为了解决这种冲突，但只是减少冲突，冲突永远存在，因为整形的值是有限的，但是字符串的可能性无穷多
      }
      return hash;
  }
};


template<class K,class V,class Hash=HashFunc<K>>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    HashTable()
    {
        _tables.resize(10);
    }
    
    ~HashTable()//对链表进行释放
    {
        for(size_t i=0;i<_tables.size();i++)
        {
            Node* cur=_tables[i];
            while(cur)
            {
                Node* next=cur->next;//释放一个节点的时候一定要记住，要保留下一个节点的地址
                delete cur;
                cur=next;
            }
            _tables[i]=nullptr;//释放完，需要对哈希表的数据置空
        }
    }
    
    bool Insert(const pair<K,V>& kv)
    {
        if(Find(kv.first))
            return false;
        
        Hash hf;//仿函数
        //负载因子,这里的负载因子最大可以为一
       if(_n==_tables.size())
        //if(_n*10/_tables.size()==7)
        {
            //这里的扩容，不能像开散列那样，因为那样是两个vector类型进行交换，释放资源，是由内部决定的，而现在，除了释放vector还要释放链表，所以这里得手动释放
            vector<Node*> newTables;//创建一个新的哈希表
            newTables.resize(_tables.size()*2,nullptr);//新的哈希表扩容到原来的2倍
            //遍历旧表
            for(size_t i=0;i<_tables.size();i++)
            {
                Node* cur =_tables[i];
                while(cur)
                {
                    Node* next=cur->next;//记录头节点的下一个位置
                    
                    //挪动到映射的新表，按照新的映射关系，将旧表数据放到新表中，这里采用的方法：对原来旧表的节点，改变他们的指向，连接到新表中，这样做可以减少空间浪费
                    size_t hashi=hf(cur->_kv.first)%newTables.size();
                    cur->next=newTables[hashi];
                    newTables[hashi]=cur;
                    
                    cur=next;//遍历一个桶的数据
                }
                _tables[i]=nullptr;//一定要置空，不然出了作用域，新表会调用析构函数，对原来数据进行释放
            }
            _tables.swap(newTables);//新表和旧表交换数据
        }
        
        size_t hashi=hf(kv.first)%_tables.size();//将关键字和哈希表建立映射
        Node* newnode=new Node(kv);//创建的节点
        
        //头插
        newnode->next=_tables[hashi];
        _tables[hashi]=newnode;
        ++_n;//关键字数据+1
        
        return true;
    }
    Node* Find(const K& key)
    {
        Hash hf;//仿函数
        size_t hashi=hf(key)%_tables.size();
        Node* cur=_tables[hashi];
        while(cur)
        {
            if(cur->_kv.first==key)
            {
                return cur;
            }
            cur=cur->next;
        }
        return nullptr;
    }
    
    bool Erase(const K& key)
    {
        size_t hashi=key%_tables.size();
        Node* cur=_tables[hashi];
        Node* parent=nullptr;
        while(cur)
        {
            if (cur->_kv.first== key)
            {
                if (parent == nullptr)//删除的头节点
                {
                    _tables[hashi] = cur->next;
                }
                else
                {
                    parent->next = cur->next;
                }
                delete cur;

                return true;
            }

            parent = cur;//在一个桶里循环查找
            cur = cur->next;
        }
        return false;
    }
    void Print()
    {
        for(size_t i=0;i<_tables.size();i++)
        {
            Node* cur=_tables[i];
            while(cur)
            {
                cout<<"["<<i<<"]->"<<cur->_kv.first<<":"<<cur->_kv.second<<endl;
                cur=cur->next;
            }
        }
    }
    size_t size()
    {
        return _n;
    }
    
    void Some()//哈希桶的结构描述
            {
                size_t bucketSize = 0;//使用桶的个数
                size_t maxBucketLen = 0;//桶的最大长度
                size_t sum = 0;//插入数据的个数
                double averageBucketLen = 0;//平均桶长度

                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    if (cur)
                    {
                        ++bucketSize;
                    }

                    size_t bucketLen = 0;
                    while (cur)
                    {
                        ++bucketLen;
                        cur = cur->next;
                    }

                    sum += bucketLen;

                    if (bucketLen > maxBucketLen)
                    {
                        maxBucketLen = bucketLen;
                    }
                }

                averageBucketLen = (double)sum / (double)bucketSize;

        printf("all bucketSize:%lu\n", _tables.size());
                printf("bucketSize:%lu\n", bucketSize);
                printf("maxBucketLen:%lu\n", maxBucketLen);
                printf("averageBucketLen:%lf\n\n", averageBucketLen);
            }
private:
    vector<Node*> _tables;//哈希表外层使用的顺序表
    size_t _n;//关键字的个数
};
void TestHT1()//测试哈希桶
{
    HashTable<int, int> ht;
    int a[]={4,14,24,34,5,7,1,15,25,3};
    for(auto e: a)
    {
        ht.Insert(make_pair(e, e));
    }
    ht.Print();
    cout<<ht.Find(4)<<endl;
    ht.Print();
    ht.Erase(4);
    cout<<ht.Find(4)<<endl;
    cout<<ht.size()<<endl;
    
    ht.Some();
}

void TestHT2()//测试哈希桶
{
    string arr[]={"苹果","香蕉","葡萄","芒果","水蜜桃","猕猴桃","胡桃","香蕉","葡萄","芒果","芒果","水蜜桃","猕猴桃","胡桃","香蕉","葡萄","芒果","火龙果","西瓜"};

    HashTable<string,int> ht;

    for(auto& ch:arr)
    {
        auto ret=ht.Find(ch);
        if(ret)
        {
            ret->_kv.second++;
        }
        else
        {
            ht.Insert(make_pair(ch, 1));
        }
    }
    ht.Print();
    cout<<ht.size()<<endl;
}
}
